package leetcode.hot100;

import java.util.HashMap;

@SuppressWarnings("all")
public class _3_无重复字符的最长子串 {

    // "abcabcbb"的无重复字符的最长子串是 "abc"，所以其长度为3
    // "bbbbb"的无重复字符的最长子串是 "b"，所以其长度为1
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        char[] chars = s.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        // 初始化第一条数据，方便后面的比较
        map.put(chars[0], 0);
        int left = 0;           //标记当前最长无重复子串的起点
        int maxSubLen = 1;      //记录当前最长无重复子串的长度
        for (int i = 1; i < chars.length; i++) {
            // pi用来判断当前字符在之前是否出现过
            int pi = map.getOrDefault(chars[i], -1);
            // 情况1：当前字符在之前没有出现过
            // 情况2：当前字符在之前出现过
            // 情况2.1：出现在---当前最长无重复子串的起点，之后---说明当前最长无重复子串起点往后不会在扩张了，更新起点营造新的可能
            // 情况2.2：出现在---当前最长无重复子串的起点，之前---对当前起点的子串扩张无影响
            // 情况2.3：出现在---和当前最长无重复子串的起点，重合---同情况2.1
            if (pi != -1 && pi >= left) {
                left = pi + 1;
            }
            maxSubLen = Math.max(maxSubLen, i - left + 1);
            // 记录被遍历的字符的位置
            map.put(chars[i], i);
        }
        return maxSubLen;
    }

}
